/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package item25;

import org.junit.Test;

/**
 * <p>
 *
 * </p>
 * @author LvJing
 * @version $Id:MergeList.java v1.0 2018/8/4 上午1:09 LvJing Exp $
 */
public class MergeList {

    /**
     * 面试题25：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
     * 思路：比较容易想到的思路是同时遍历两个链表，依次取值进行判断和拼接，最后拼接完成的链表就是最终单调递增的链表。
     */
    public class Solution {
        public ListNode Merge(ListNode list1, ListNode list2) {
            if (list1 == null) {
                return list2;
            }
            if (list2 == null) {
                return list1;
            }

            ListNode mergeHead = null;
            ListNode currentNode = null;
            while (list1 != null && list2 != null) {
                if (list1.val <= list2.val) {
                    if (mergeHead == null) {
                        mergeHead = currentNode = list1;
                    } else {
                        currentNode.next = list1;
                        currentNode = currentNode.next;
                    }
                    list1 = list1.next;
                } else {
                    if (mergeHead == null) {
                        mergeHead = currentNode = list2;
                    } else {
                        currentNode.next = list2;
                        currentNode = currentNode.next;
                    }
                    list2 = list2.next;
                }
            }

            if (list1 == null) {
                currentNode.next = list2;
            } else {
                currentNode.next = list1;

            }

            return mergeHead;
        }
    }

    public class ListNode {
        int      val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    @Test
    public void test01() {
        ListNode list1 = new ListNode(1, new ListNode(3, new ListNode(5, new ListNode(7, null))));
        ListNode list2 = new ListNode(2, new ListNode(4, new ListNode(6, new ListNode(8, null))));
        ListNode mergeHead = new Solution().Merge(list1, list2);
        printListNode(mergeHead);
    }

    private void printListNode(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " | ");
            head = head.next;
        }
        System.out.println("");
    }
}
